#include <iostream>

using namespace std;

// KMP算法的实现

// 获取最长公共先后缀
int* getLpsList(int arr[],int length)
{
    int* reArr=new int[length];
    reArr[0]=0;
    reArr[1]=1;
    for(int i=2;i<length;i++)
    {
        int left=0,right=i-1;
        while(right!=0 && arr[left]==arr[right])
        {
            left++;
            right--;
        }
        reArr[i]=left+1;
    }
    return reArr;
}

void GetNext(int *p,int *next,int length)
{
	int pLen=length;
	next[0]=-1;
	int k=-1;
	int j=0;
	while(j<pLen){
		if(k==-1||p[k]==p[j]){
			k++;
			j++;
			next[j]=k;
		}else{
			k=next[k];
		}
	}
    next[0]=0;
}

// 主算法的实现
int KMPSearch(int searchArr[],int targetArr[],int nextArr[],int searchLen,int targetLen)
{
    int i=0,k=0;
    while(i<searchLen && k<targetLen)
    {
        if(searchArr[i]==targetArr[k])
        {
            i++;
            k++;
        }
        else
        {
            i++;
            k=nextArr[k];
        }
    }
    if(k==targetLen)
    {
        return i-targetLen;
    }
    else
    {
        return -1;
    }
}

int main()
{
    int arr[]={1,1,1,2};
    int target[11]={1,1,1,3,2,2,1,1,1,2,3};
    int length=sizeof(arr)/sizeof(int);
    int *reArr=new int[length];
    GetNext(arr,reArr,length);
    for(int i=0;i<length;i++)
    {
        cout<<reArr[i]<<' ';
    }
    cout<<endl;

    cout<<KMPSearch(target,arr,reArr,11,4)<<endl;
}